package treesNgraphs;

/**
 * Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
 */
public class ArrayToTree {

    public static TreeNode<Integer> arrayToTree(int[] array, int startIndex, int endIndex) {
        if (endIndex - startIndex == 0) {
            return new TreeNode<>(array[startIndex]);
        }

        if (endIndex - startIndex == 1) {
            TreeNode<Integer> node = new TreeNode<>(array[endIndex]);
            node.setLeftChild(new TreeNode<>(array[startIndex]));
            return node;
        }

        if (endIndex - startIndex == 2) {
            TreeNode<Integer> node = new TreeNode<>(array[startIndex + 1]);
            node.setLeftChild(new TreeNode<>(array[startIndex]));
            node.setRightChild(new TreeNode<>(array[endIndex]));
            return node;
        }

        int pos = (endIndex - startIndex) / 2;
        TreeNode<Integer> treeNode = new TreeNode<>(array[pos]);
        treeNode.setLeftChild(arrayToTree(array, startIndex, pos - 1));
        treeNode.setRightChild(arrayToTree(array, pos + 1, endIndex));
        return treeNode;
    }


    public static void main(String[] args) {
        TreeNode treeNode = arrayToTree(new int[]{1, 2, 3, 4, 5, 6, 7}, 0, 6);
        System.out.println();
    }
}
